﻿using System;

namespace FindDihotTDD
{
    public class SearchDichotomy
    {
        
        public int dichotSearch(int[] mas, int x)
        {
            Array.Sort(mas);
            int first = 0;
            int last = mas.Length;
            int mid;

            if (mas.Length == 0)
            {
                throw new Exception();
            }
            if (mas.Length == 1)
            {
                if (mas[0] == x)
                    return 0;
                else throw new Exception("Element not found");
            }
            else if (mas[0] > x)
            {
                throw new Exception("Element not found");
            }
            else if (mas[mas.Length - 1] < x)
            {
                throw new Exception("Element not found");
            }

            while (first < last)
            {
                mid = first + (last - first) / 2;

                if (x <= mas[mid])
                {
                    last = mid;
                }
                else
                {
                    first = mid + 1;
                }
            }

            if (mas[last] == x)
            {
                return last;
            }
            else
            {
                throw new Exception("Element not found");
            }
        }
    }
}
